package interview.huawei.training.p50;

import java.util.*;

/**
 * 字符版本，不能处理超过2位数的计算
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 中缀表达式转后缀表达式
        ArrayList<Character> postfixList = infixToPostfix(scanner.nextLine());
         System.out.println(postfixList);
        // 根据后缀表达式计算结果
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (Character ch : postfixList) {
            if (!Character.isDigit(ch)) {
                char num1 = stack.pop();
                char num2 = stack.pop();
                int res = 0;
                switch(ch) {
                    case '+': res = num1 + num2; break;
                    case '-': res = num1 - num2; break;
                    case '*': res = num1 * num2; break;
                    case '/': res = num1 / num2; break;
                }
                // 计算结果再入栈
                stack.push(ch);

            }
            // 数字直接入栈
            else {
                stack.push(ch);
            }
        }
    }

    // 中缀表达式转后缀表达式
    private static ArrayList<Character> infixToPostfix(String infixStr) {
        ArrayList<Character> infixList = new ArrayList<>();
        // 解决负数的问题，如 -1 + 1
        // 即在 -1 前面加一个0 变成  0-1 即可
        // 情况1：第1个字符是负号
        char c = infixStr.charAt(0);
        if (c == '-') {
            infixList.add('0');
        }
        infixList.add(c);
        // 情况2：( [ { 等字符后面是负号
        for (int i = 1; i < infixStr.length(); i++) {
            c = infixStr.charAt(i - 1);
            char nextC = infixStr.charAt(i);
            if ((c == '(' || c == '[' || c == '{') && nextC == '-') {
                infixList.add('0');
            }
            infixList.add(nextC);
        }

        // 将中缀表达式转成后缀表达式
        ArrayList<Character> postfixList = new ArrayList<>();
        // 符号栈
        ArrayDeque<Character> signStack = new ArrayDeque<>();
        for (Character ch : infixList) {
            Character topSign = signStack.peek();
            switch (ch) {
                case '+':
                case '-':
                    // 如果符号栈的栈顶元素的优先级不低于当前运算符
                    // 栈顶元素出栈后放进后缀表达式数组中
                    while (!signStack.isEmpty() && (topSign == '*' || topSign == '/' || topSign == '+' || topSign == '-')) {
                        postfixList.add(signStack.pop());
                        topSign = signStack.peek();
                    }
                    // 将加减符号放进符号栈
                    signStack.push(ch);
                    break;
                case '*':
                case '/':
                    // 如果符号栈的栈顶元素的优先级不低于当前运算符
                    // 栈顶元素出栈后放进后缀表达式数组中
                    while (!signStack.isEmpty() && (topSign == '*' || topSign == '/')) {
                        // */的优先级不低于当前运算符，所以要出栈，加减的优先级低于当前运算符，不予处理
                        postfixList.add(signStack.pop());
                        topSign = signStack.peek();
                    }
                    // 将乘除符号放进符号栈
                    signStack.push(ch);
                    break;
                case '(':
                case '[':
                case '{':
                    // 遇到左括号直接加入符号栈
                    signStack.push(ch);
                    break;
                case ')':
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && topSign != '(') {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                case ']':
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && topSign != '[') {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                case '}':
                    // 遇到右括号，一直出栈直到匹配到左括号，且当前右括号不入符号栈
                    topSign = signStack.pop();
                    while (!signStack.isEmpty() && topSign != '{') {
                        postfixList.add(topSign);
                        topSign = signStack.pop();
                    }
                    break;
                default: postfixList.add(ch);
            }
        }

        while(!signStack.isEmpty()) {
            postfixList.add(signStack.pop());
        }

        return postfixList;
    }
}